package sword.T43;

/**
 * @Author: 18362
 * @Create: 2022-04-09 10:00:27 星期六
 */

class Solution {
    public int countDigitOne(int n) {
        String num = String.valueOf(n);
        int[][] table = getTable(num);
        return getCount(num, 0, table);
    }

    private int getCount(String num, int start, int[][] table) {
        int digit = num.charAt(start) - '0';
        if (start == num.length()-1)
            return table[0][digit];
        int count = getCount(num, start+1, table);
        if (digit == 0) {
            return count;
        } else if (digit > 1) {
            return count + table[num.length()-start-1][digit-1];
        } else {
            return count + Integer.parseInt(num.substring(start+1)) + 1 + table[num.length()-start-1][0];
        }
    }

    private int[][] getTable(String num) {
        int[][] table = new int[num.length()][10];
        int base = 1;
        for (int i=0; i<table.length; ++i) {
            if (i > 0)
                table[i][0] = table[i-1][9];
            table[i][1] = base + table[i][0]*2;
            for (int j=2; j<=9; ++j) {
                table[i][j] = table[i][j-1] + table[i][0];
            }
            base *= 10;
        }
        return table;
    }
}